{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## 插入排序算法",
   "id": "bbc7fb56fac3809f"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 插入升序排序\n",
    "def insertSortArc(arr: list) -> list:\n",
    "    length = len(arr)\n",
    "    for i in range(1, length):\n",
    "        temp = arr[i]\n",
    "        j: int = i - 1\n",
    "        while j >= 0 and arr[j] > temp:\n",
    "            arr[j + 1] = arr[j]\n",
    "            j -= 1\n",
    "        arr[j + 1] = temp\n",
    "\n",
    "    return arr\n",
    "\n",
    "\n",
    "# 插入降序排序\n",
    "def insertSortDesc(arr: list) -> list:\n",
    "    length = len(arr)\n",
    "    for i in range(1, length):\n",
    "        temp = arr[i]\n",
    "        j: int = i - 1\n",
    "        while j >= 0 and arr[j] < temp:\n",
    "            arr[j + 1] = arr[j]\n",
    "            j -= 1\n",
    "        arr[j + 1] = temp\n",
    "    return arr"
   ],
   "id": "4faf90d703c98ee7",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr: list = random.sample(range(100), 100)\n",
    "print(arr)\n",
    "insertSortDesc(arr)\n",
    "print(arr)"
   ],
   "id": "96d100e49b121d07",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "#### 线性查找一个序列中地一个值，存在时输出下标，不存在输出Null",
   "id": "295f9fe6a6892db0"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def findNumer(arr: list, num: int) -> int | None:\n",
    "    flag: bool = False\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i] == num:\n",
    "            flag = True\n",
    "            return i\n",
    "    if not flag:\n",
    "        return None"
   ],
   "id": "4184657b40c90a54",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "arr: list = random.sample(range(100), 100)\n",
    "print(arr)\n",
    "print(findNumer(arr, 55))"
   ],
   "id": "87b4a8731866409b",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "#### 考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个(n+ 1)元数组C中。",
   "id": "5cb706b918ea110d"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def binaryAdd(num1: list, num2: list) -> list:\n",
    "    # reverse方法会直接修改原始列表，而不需要重新赋值，其返回值恒为None\n",
    "    num1.reverse()\n",
    "    num2.reverse()\n",
    "    if len(num1) < len(num2):\n",
    "        num1, num2 = num2, num1\n",
    "    check = len(num2)\n",
    "    next: bool = False\n",
    "    ans = []\n",
    "    for i in range(check):\n",
    "        # 下一位的补偿值在上一位的补偿值和当前的两个被加数（3个值）其中有单数个true即为true\n",
    "        ans.append((num1[i] ^ num2[i]) ^ next)\n",
    "        # 下一位的补偿值在上一位的补偿值和当前的两个被加数（3个值）其中有2个以上为true即为true\n",
    "        next = num1[i] if num1[i] == num2[i] else next\n",
    "\n",
    "    for i in range(check, len(num1)):\n",
    "        ans.append(num1[i] ^ next)\n",
    "        next = num1[i] & next\n",
    "    ans.reverse()\n",
    "    return ans"
   ],
   "id": "a36b3f612a7b0ac7",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def bool2binary(num: list) -> str:\n",
    "    ans = ''\n",
    "    for item in num:\n",
    "        ans += '1' if item else '0'\n",
    "    return ans"
   ],
   "id": "e0cae3abdb7eaa4c",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "num1: list = random.choices([True, False], k=10)\n",
    "num2: list = random.choices([True, False], k=15)\n",
    "print(num1)\n",
    "print(bool2binary(num1))\n",
    "print(num2)\n",
    "print(bool2binary(num2))\n",
    "ans = binaryAdd(num1, num2)\n",
    "print(ans)\n",
    "print(bool2binary(ans))"
   ],
   "id": "21e84ffb3264b2f4",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "#### 选择排序",
   "id": "3d09b425e7981090"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def selectSort(arr: list) -> list:\n",
    "    for i in range(0, len(arr)):\n",
    "        minIndex = i\n",
    "        for j in range(i + 1, len(arr)):\n",
    "            minIndex = j if arr[j] < arr[minIndex] else minIndex\n",
    "        arr[i], arr[minIndex] = arr[minIndex], arr[i]\n",
    "    return arr"
   ],
   "id": "c57e981d597fa28d",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "arr: list = random.sample(range(100), 100)\n",
    "print(arr)\n",
    "print(selectSort(arr))"
   ],
   "id": "1926f800042e0578",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "#### 归并排序",
   "id": "526a7a036f34ac32"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def merge(arr: list, l: int, mid: int, r: int) -> None:\n",
    "    temp = []\n",
    "    pl = l\n",
    "    pr = mid + 1\n",
    "    while pl <= mid and pr <= r:\n",
    "        if arr[pl] <= arr[mid]:\n",
    "            temp.append(arr[pl])\n",
    "            pl += 1\n",
    "        else:\n",
    "            temp.append(arr[pr])\n",
    "            pr += 1\n",
    "    while pl <= mid:\n",
    "        temp.append(arr[pl])\n",
    "        pl += 1\n",
    "    while pr <= r:\n",
    "        temp.append(arr[pr])\n",
    "        pr += 1\n",
    "    for i in range(l, r + 1):\n",
    "        arr[i] = temp[i]\n",
    "    return\n",
    "\n",
    "\n",
    "def mergeSort(arr: list, l: int, r: int) -> None:\n",
    "    if l < r:\n",
    "        mid = (l + r) / 2\n",
    "        mergeSort(arr, l, mid)\n",
    "        mergeSort(arr, mid + 1, r)\n",
    "        merge(arr, l, mid, r)\n",
    "    return "
   ],
   "id": "39e21fa23d7840ba",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "import random\n",
    "arr: list = random.sample(range(100), 100)\n",
    "print(arr)\n",
    "print(selectSort(arr))"
   ],
   "id": "89fe7cce242c024b",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "#### 二分查找",
   "id": "56a9156a6b534c1c"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "def binarySearch(arr:list, key:int, l:int, r:int) -> int:\n",
    "    mid = len(arr) / 2\n",
    "    if key == arr[mid]:\n",
    "        return mid\n",
    "    elif key < arr[mid]:\n",
    "        return binarySearch(arr, key, l, mid - 1)\n",
    "    else:\n",
    "        return binarySearch(arr, key, mid + 1, r)"
   ],
   "id": "91593f58dbda1360"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
